System testing contributes significantly to system development and maintenance costs. TestMaster(copyright) software sold by Teradyne(copyright) Software and System Test, Inc. of Nashua, NH can reduce testing costs while increasing testing quality.
Referring to FIG. 1, TestMaster(copyright) software 100 enables a designer to create 102 an extended finite state machine model of a system. An extended finite state machine is represented by a directed graph that includes states interconnected by transitions. The software 100 provides a graphical user interface that enables the designer to xe2x80x9cdrawxe2x80x9d the model by defining the states and connecting them together with directional lines that represent transitions. The model is independent of the system being modeled and can be created before or after the system is developed.
After the designer creates 102 the model, the software 100 detects 104 paths through the model states and transitions and generates 106 testing programs corresponding to each of the detected paths. Execution of the generated testing programs can identify system design flaws and highlight differences between the model created and the actual behavior of the underlying system.
Referring to FIG. 2, an extended finite state machine model 108 of a system includes states 110-116 interconnected by transitions 118-124. For example, as shown, a model 108 includes states 110-116 and transitions 118-124 representing a bank machine system that dispenses cash to customers entering an authorized PIN (Personal Identification Number).
The TestMaster(copyright) system automatically detects different paths through the model 108. For example, as shown in FIG. 3, a path through the model can include model elements A-TAB-B-TBC-C-TCD-D. This path corresponds to a customer correctly entering an authorized PIN and successfully withdrawing cash. As shown in FIG. 4, a different path through the model can include model elements A-TAB-B-TBD-D. This model path corresponds to a customer who fails to correctly enter an authorized PIN.
TestMaster(copyright) offers many different procedures for detecting paths through a model. For example, a user can select from comprehensive, transition-based, N-switch, and quick-cover path detection. Comprehensive path detection outputs a test for every possible path through the model. Transition based path detection outputs tests such that each transition is included in at least one test. N-switch path detection outputs tests such that each unique sequence of N+1 transitions are included in at least one test. Comprehensive, transition, and N-switch path detection are currently implemented using a depth-first search. In contrast, quick-cover uses a xe2x80x9ctop-downxe2x80x9d search and can output tests such that no transition is used more than a specified number of times. U.S. patent application No. 08/658,344 entitled xe2x80x9cMethod and Apparatus for Adaptive Coverage in Test Generationxe2x80x9d describes implementations of programs for detecting extended finite state machine paths.
Referring again to FIG. 2, in addition to transitions and states, a model can incorporate variables and expressions that further define the model""s behavior. TestMaster(copyright) can evaluate the expressions to assign variable values (e.g., y=mx+b) or to determine whether an expression is TRUE or FALSE (e.g., A AND (B OR C)). The expressions can include operators, variables, and other elements such as the names of states, transitions, and/or sub-models. When a named state, transition, or sub-model is in included in an expression, the model element evaluates to TRUE when included in the path currently being detected. For example, in FIG. 2, an expression of xe2x80x9c(A andand B)xe2x80x9d would evaluate to TRUE for path portion xe2x80x9cA-TAB-Bxe2x80x9d. As shown, expressions can use a PFL (Path Flow Language) syntax that resembles the C programming language. PFL and functions that can be called from PFL are described in The TestMaster(copyright) Reference Guide published by Teradyne(copyright).
A model designer can associate the expressions with model elements to further define model behavior. For example, a designer can associate predicates and/or constraints with different states, transitions, and/or sub-models. Both predicates and constraints are evaluated during path detection and determine which transitions can be included in a path.
When path detection instructions encounter a model element having an associated predicate, the predicate expression is evaluated. If the predicate evaluates to TRUE, the model element associated with the predicate can be used in the path. For example, as shown in FIG. 2, transition TBD 124 has an associated predicate 126 (xe2x80x9c!OKPinxe2x80x9d) that determines when a path can include the transition. As shown, the predicate 126 is a boolean expression that permits inclusion of the transition 124 in a path being detected when the boolean variable OKPin is FALSE and the path being detected has reached state B.
Similarly, when path detection instructions encounter a model element having an associated constraint, the constraint expression is evaluated. If the constraint evaluates to FALSE, the model element associated with the constraint cannot be used in the path being detected. For example, as shown in FIG. 2, a transition 123 can connect a state 114 to itself. To prevent a path from including a large or possibly infinite number of the same transition in a single path, a designer can specify a constraint expression 125 that limits use of a transition in a path. The xe2x80x9cIterate(3)xe2x80x9d expression associated with the transition 123 limits a path through the model to including transition 123 three times. Thus, if evaluated at state C after looping around transition TCC three times, the constraint would evaluate to FALSE and prevent further use of the transition in the current path. The constraint acts as a filter, eliminating generation of unwanted testing programs.
Referring to FIG. 5, a model can also include one or more sub-models. For example, the box labeled xe2x80x9cEnterPINxe2x80x9d in FIG. 2 may be a sub-model 112 that includes additional states 128-136, transitions 138-150, and expressions. As shown, the sub-model 112 sets 150 the model variable OKPin to TRUE when the customer PIN equals 1 148; otherwise, the sub-model sets the model variable OKPin to FALSE 146.
Sub-models encourage modular system design and increase comprehension of a model""s design. Referring to FIG. 6, when the software 100 detects different paths through the system, the sub-model is essentially replaced with the states and transitions included in the sub-model.
Referring again to FIG. 5, a designer can define more than one transition 138-142 between states 128, 130. The designer can also associate expressions (e.g., PIN=1) with each transition 138-142, for example, to set model variables to different values. For example, as shown, a designer has defined three transitions between the xe2x80x9cEntryxe2x80x9d 128 and xe2x80x9cPINEntryxe2x80x9d 130 states that each set a PIN variable to different value. Defining multiple transitions between states increases the number of paths through a model. For example, paths through the sub-model 112 can include I-TIJ(1)-J-TJK-K-TKM-M, I-TIJ(2)-J-TJL-L-TLM-M, and I-TIJ(3)-J-TJL-L-TLM-M. The use of multiple transitions enables testing of different conditions within the same model.
In general, in one aspect, a method of using a computer to analyze an extended finite state machine model of a system includes receiving at least one requirement expression, determining at least one path of states and transitions through the model, evaluating at least one of the requirement expressions based on at least one of the determined paths through the model to determine whether the path satisfies the requirement expression, and generating a report based on the evaluating.
EFSMAs are known to those of ordinary skill in the art. EFSMAs are described in detail in U.S. Pat. No. 5,918,037 (the ""037 patent). As described in the ""037 patent the EFSMA can be drawn out in a tree diagram. States (e.g. S1, S2, and S3) of a call to the model are represented as nodes of the tree (e.g. A1, A2, A3). The transitions (e.g. T1, T2, T3, T4 and T5) are represented as branches interconnecting the nodes. Paths through the EFSMA are generated by doing a depth first search through the tree structure. The search is kept track of by use of a model stack and a path stack. As each transition is traced out, an indication of that node and transition is pushed onto the path stack. As the path crosses from one model into the next, a new frame is pushed onto the model stack.
Each entry on the path stack is a pair of values, representing a state and transition from that state. For example, the entries in the path stack may indicate that the path was traced in the following order: (A1, T1), (A2, T3), (A3, T5), (B1, X). The model stack may show that the Path 1 goes through Models A and B.
Once a complete path has been generated through the EFSMA, the next path is generated by popping a frame from the path stack and, if the transition popped from the path stack was to the entry state of a model, a frame is popped from the model stack as well. Once a frame is popped from the top of the path stack, the new frame at the top of the stack includes value representing a transition into one of the states in the EFSMA, If there is an xe2x80x9cacceptablexe2x80x9d transition out of that state, another frame is pushed on the path stack indicating that transition. Items are again pushed on the stack until a complete path has been generated.
Where there is no acceptable transition, another frame is popped from the path stack, leaving a transition to a different state at the top of the path stack. Once again, a check is made of whether there is an acceptable transition out of this state. Frames are popped from the stack until there is a transition is at the top of the stack that leads to a state from which there is another xe2x80x9cacceptablexe2x80x9d transition.
Once an xe2x80x9cacceptablexe2x80x9d transition is reached, items are then pushed onto the stack until a terminal state of the EFSMA is reached. At this point, the path stack contains a new path. The process continues in this fashion, pushing and popping items onto the path stack until, at some point, all the transitions are popped from the path stack without reaching a state that has an xe2x80x9cacceptablexe2x80x9d transition.
An xe2x80x9cacceptablexe2x80x9d transition is identified by selecting a transition from that state that has not been used at that point in a path. For example, when state A2 is placed on the stack at a particular point P, there must be some way to keep track of the two transitions, T3 and T2 from that state. Transition T3 is included in Path 1. When the stack frame represented by that point P is pushed on the stack, a data structure could be set-up to show that there are transitions T2 and T3 from that state. When Path 1 is traced out, the data structure would be update to show that transition T3 had been taken from that point P. Thus, when the path stack is popped again to point P, the data structure shows that transition T2 has not been taken from that point.
In this way, all paths are traced out without duplication. Of course, if a particular transition violates a user specified constraint, it is not considered xe2x80x9cacceptable.xe2x80x9d Likewise, when the model specifies that only certain transitions are allowed in certain circumstances, a check must be made whether those circumstances exist before a transition is considered acceptable.
Embodiments include one or more of the following. The report includes a report of paths satisfying at least one requirement. The report includes a report of requirements satisfied by a path. The requirement expression comprises a Boolean expression. The requirement expression further includes a variable, an operator, a state, a transition, a sub-model, a table-model, and/or another requirement expression. The method generates testing programs only for paths satisfying a specified requirement or set of requirements.
In general, in another aspect, a method of using a computer to analyze an extended finite state machine model of a system includes receiving a requirement expression, determining at least one path of states and transitions through the model, evaluating at least one of the requirement expressions based on at least one of the determined paths through the model to determine whether the path satisfies the requirement expression, and including the requirement expression as an element in a different expression, the evaluation of the requirement expression in the different expression depending on the determination of whether the path satisfies the requirement expression.
In general, in another aspect, a method of using a computer to analyze an extended finite state machine model of a system includes receiving at least one assertion expression, evaluating the assertion expression based on a path being determined through the model, and if the evaluation indicates the path being determined fails to satisfy the assertion expression, indicating the failure.
Embodiments may include one or more of the following features. The method may further include halting model path determination. The assertion expression may be a boolean expression. The assertion expression may include a variable, an operator, a state, a transition, a sub-model, a table-model, and/or a requirement. The method may further include initiating a debugger if the evaluation indicates the path being determined fails to satisfy the assertion expression. The method may include receiving user input specifying when the assertion expression is evaluated. Specifying when the assertion expression is evaluated may be performed by specifying a model element.
The method may include automatically evaluating the assertion expression after a complete path through the model has been determined and/or automatically evaluating the assertion expression as model elements are added to a path being determined.
In general, in another aspect, a computer program product, disposed on a computer readable medium, for analyzing an extended finite state machine model of a system, includes instructions for causing a processor to receive at least one requirement expression, determine at least one path of states and transitions through the model, evaluate at least one of the requirement expressions based on at least one of the determined paths through the model to determine whether the path satisfies the requirement expression, and generate a report based on the evaluating.
In general, in another aspect, a computer program product, disposed on a computer readable medium, for analyzing an extended finite state machine model of a system includes instructions for causing a processor to receive a requirement expression, determine at least one path of states and transitions through the model, evaluate at least one of the requirement expressions based on at least one of the determined paths through the model to determine whether the path satisfies the requirement expression, and include the requirement expression as an element in a different expression, the evaluation of the requirement expression in the different expression depending on the determination of whether the path satisfies the requirement expression.
In general, in another aspect, a computer program product, disposed on a computer readable medium, for analyzing an extended finite state machine model of a system includes instructions for causing a processor to receive at least one assertion expression, evaluate the assertion expression based on a path being determined through the model, and if the evaluation indicates the path being determined fails to satisfy the assertion expression, indicate the failure.